class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> ret;
        unordered_map<int, vector<int>> edges;  //存放边，邻接表
        vector<int> in(numCourses);                         //记录每个顶点的入度

        //建图
        for (int i = 0; i < prerequisites.size(); i++)
        {
            int a = prerequisites[i][0], b = prerequisites[i][1];   //b -> a
            edges[b].push_back(a);
            in[a]++;
        }

        //bfs
        queue<int> q;
        //将所有入度为0的顶点放入队列
        for (int i = 0; i < numCourses; i++)
            if (in[i] == 0)
                q.push(i);
        
        while (q.size())
        {
            int point = q.front();
            q.pop();
            //将顶点放入返回数组
            ret.push_back(point);

            //消除和point点关联的边
            //如果有新的顶点入度为0，就添加到队列
            for (int e : edges[point])
            {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }
        }

        //如果拓扑排序后还有入度不为0的点，就说明有向图中有环
        for (auto e : in)
            if (e)
                return vector<int>();
        
        return ret;
    }
};